Section: New Results

Model Specific Developments and Applications

Participants : Andrew Miller, Arnaud Pêcher, Pierre Pesneau, Ruslan Sadykov, Gautier Stauffer, François Vanderbeck.

The models on which we made progress can be partitioned in three areas: “Packing and Covering Problems”, “Network Design and Routing”, and “Planning, Scheduling, and Logistic Problems”.

Bin-Packing with Conflicts

The bin-packing problem consists in finding the minimum number of bin of fixed size one needs to pack a set of items of different sizes. We studied a generalization of this problem where items can be in conflicts and thus cannot be put together in the same bin. We show in [20] that the instances of the literature with 120 to 1000 items can be solved to optimality with a generic Branch-and-Price algorithm, such as our prototype BaPCod, within competitive computing time. Moreover, we solved to optimality all the 37 open instances. The approach involves generic primal heuristics, generic branching, but a specific pricing procedure.

Using graph theory for solving orthogonal knapsack problems

We investigated the orthogonal knapsack problem, with the help of graph theory. The multi-dimensional orthogonal packing problem (OPP) is defined as follows: given a set of items with rectangular shapes, the problem is to decide whether there is a non-overlapping packing of these items in a rectangular bin. The rotation of items is not allowed. A powerful characterization of packing configurations by means of interval graphs was introduced by Fekete and Schepers using an efficient representation of all geometrically symmetric solutions by a so called packing class involving one interval graph (whose complement admits a transitive orientation: each such orientation of the edges corresponds to a specific placement of the forms) for each dimension. Though Fekete & Schepers' framework is very efficient, we have however identified several weaknesses in their algorithms: the most obvious one is that they do not take advantage of the different possibilities to represent interval graphs.

In [12] , [11] , we give two new algorithms: the first one is based upon matrices with consecutive ones on each row as data structures and the second one uses so-called MPQ-trees, which were introduced by Korte and Mohring to recognize interval graphs. These two new algorithms are very efficient, as they outperform Fekete and Schepers' on most standard benchmarks.

Inventory routing and logistics problems

Inventory routing problems combine the optimization of product deliveries (or pickups) with inventory control at customer sites. in [13] , we considered the planning of single product pickups over time: each site accumulates stock at a deterministic rate; the stock is emptied on each visit. Our objective is to minimize a surrogate measure of routing cost while achieving some form of regional clustering by partitioning the sites between the vehicles. The fleet size is given but can potentially be reduced. Planning consists in assigning customers to vehicles in each time period, but the routing, i.e., the actual sequence in which vehicles visit customers, is considered as an “operational” decision. We developed a truncated branch-and-price algorithm. This exact optimization approach is combined with rounding and local search heuristics to yield both primal solutions and dual bounds that allow us to estimate the deviation from optimality of our solution. We were confronted with the issue of symmetry in time that naturally arises in building a cyclic schedule (cyclic permutations along the time axis define alternative solutions). Central to our approach is a state-space relaxation idea that allows us to avoid this drawback: the symmetry in time is eliminated by modeling an average behavior. Our algorithm provides solutions with reasonable deviation from optimality for large scale problems (260 customer sites, 60 time periods, 10 vehicles) coming from industry. The subproblem is interesting in its own right: it is a multiple-class integer knapsack problem with setups. Items are partitioned into classes whose use implies a setup cost and associated capacity consumption.

Scheduling

Cross docking terminals allow companies to reduce storage and transportation costs in a supply chain. At these terminals, products of different types from incoming trucks are unloaded, sorted, and loaded to outgoing trucks for delivery. In [19] , we focus on the operational activities at a cross docking terminal with two doors: one for incoming trucks and another one for outgoing trucks. We consider the truck scheduling problem with the objective to minimize the storage usage during the product transfer inside the terminal. Our interest in this problem is mainly theoretical. We show that it is NP-hard in the strong sense even if there are only two product types. For a special case with fixed subsequences of incoming and outgoing trucks, we propose a dynamic programming algorithm, which is the first polynomial algorithm for this case. The results of numerical tests of the algorithm on randomly generated instances are also presented.

In [18] , we consider the scheduling jobs in parallel, i.e., jobs can be executed on more than one processor at the same time. With the emergence of new production, communication and parallel computing system, the usual scheduling requirement that a job is executed only on one processor has become, in many cases, obsolete and unfounded. In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time (or mean weighted flow time). For this problem, we introduce the class of “ascending” schedules in which, for each job, the number of machines assigned to it cannot decrease over time while this job is being processed. We prove that, under a natural assumption on the processing time functions of jobs, the set of ascending schedules is dominant for the problem. This result can be used to reduce the search space while looking for an optimal solution.

Currently, we are working on a scheduling application at a port. For this application, an equipment routing task scheduling problem [28] has been formulated, where a set of tasks needs to be performed. Tasks require equipment of different types. A particularity of the problem is that an equipment needs to be moved to the actual locations of tasks which use this equipment. So, there are both scheduling and routing decisions are to be taken simultaneously.

One warehouse multi-retailer problem

The One-Warehouse Multi-retailer problem (OWMR) is a very important NP-hard inventory control problem arising in the distribution of goods when one central warehouse is supplying a set of final retailers facing demand from customers. In [22] , we provide a simple and fast 2-approximation algorithm for this problem (i.e. an algorithm ensuring a deviation by a factor at most two from the optimal solution). This result is both important in practice and in theory as it allows to approximate large real-world instances of the problem (we implemented this algorithm at IBM and it is within 10% of optimality in practice) and the techniques we developed appear to apply to more general settings. We are extending our results to other inventory control problems.